package codingforgreat.lchot150;

import java.util.Stack;

public class Lc084 {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int height = 0;
        for(int i = 0;i < heights.length;i++){
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                int  index = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                res = Math.max((i - k - 1)*heights[index] , res);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            res = Math.max((heights.length - k - 1)*heights[index] , res);
        }
        return res;
    }
}
